package testcases;

public class HeapSort {
    public static void main(String[] args) {
        int length = 10;
        int[] a = {5, 2, 3, 9, 6, 4, 15, 1, 6, 90};
        System.out.println("Following is Unsorted input array");
        for (int i = 0; i < length; i++) {
            System.out.print(a[i] + " ");
        }

        for (int i = a.length; i > 1; i--) {
            sort_heap(a, i - 1);
        }
        System.out.println("Sorted Heap  ::::::: ");
        for (int j = 0; j < a.length; j++) {
            System.out.print("  " + a[j]);
        }
    }

    public static void sort_heap(int[] a, int heap_size) {

        int lchild, rchild, root, largest;

        root = (heap_size - 1) / 2;
        for (int i = root; i >= 0; i--) {
            for (int j = root; j >= 0; j--) {
                lchild = (2 * j) + 1;
                rchild = lchild + 1;
                if ((lchild <= heap_size) && (rchild <= heap_size)) {
                    if (a[rchild] >= a[lchild]) {
                        largest = rchild;
                    } else largest = lchild;
                } else {
                    if (rchild > heap_size)
                        largest = lchild;
                    else
                        largest = rchild;
                }
                if (a[j] < a[largest]) {
                    swap(a, i, largest);
                }
            }
        }
        swap(a, 0, heap_size);
        return;

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
